Turing Maschine

Die Turingmaschine hat ein Steuerwerk, in dem sich das Programm befindet, und besteht außerdem aus einem unendlich langen Speicherband mit unendlich vielen sequentiell angeordneten Feldern. Pro Feld kann genau ein Zeichen aus einem vordefinierten Alphabet gespeichert werden. Als zusätzliches Zeichen ist ein Blank (englisch für „leer/unbeschrieben“) zugelassen, das einem leeren Feld auf dem Speicherband entspricht. einem programmgesteuerten Lese- und Schreibkopf, der sich auf dem Speicherband feldweise bewegen und die Zeichen verändern (im Fall eines zu ‚schreibenden‘ Blanks auch löschen) kann. Die Turingmaschine modifiziert die Eingabe auf dem Band nach dem festgelegten Programm. Die Startposition der Turingmaschine ist am Anfang des Eingabeworts, d. h. an der Position des ersten Eingabezeichens. Mit jedem Schritt liest der Lese-Schreib-Kopf das aktuelle Zeichen, überschreibt dieses mit einem anderen (oder dem gleichen) Zeichen und bewegt sich dann ein Feld nach links oder rechts oder bleibt stehen. Welches Zeichen geschrieben wird und welche Bewegung ausgeführt wird, hängt von dem an der aktuellen Position vorgefundenen Zeichen sowie dem Zustand ab, in dem sich die Turingmaschine gerade befindet. Dies wird durch eine zu der Turingmaschine gehörende Überführungsfunktion definiert. Zu Beginn befindet sich die Turingmaschine in einem vorgegebenen Startzustand und geht bei jedem Schritt in einen neuen Zustand über. Die Anzahl der Zustände, in denen sich die Turingmaschine befinden kann, ist endlich. Ein Zustand kann mehrere Male durchlaufen werden, er sagt nichts über die auf dem Band vorliegenden Zeichen aus. Eine Turingmaschine stoppt, wenn für den aktuellen Zustand und das gelesene Bandsymbol keine Überführung zu einem neuen Zustand definiert ist. Es hängt also im Allgemeinen von der Kombination aus Zustand und Symbol ab, ob die Turingmaschine weiter rechnet oder stoppt. Zustände, in denen die Turingmaschine unabhängig von dem gelesenen Bandsymbol anhält, bezeichnet man als Endzustände. Es gibt aber auch Turingmaschinen, die für gewisse Eingaben niemals stoppen. Neben der Berechnung von Funktionen wird die Turingmaschine – wie viele andere Automaten – auch für Entscheidungsprobleme eingesetzt, also für Fragen, die mit „ja“ oder „nein“ zu beantworten sind. Bestimmte Endzustände werden als „akzeptierend“, andere als „nicht akzeptierend“ definiert. Die Eingabe wird genau dann akzeptiert, wenn die Turingmaschine in einem akzeptierenden Endzustand endet.